package Heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于整型最大堆的实现
 * 若此时根节点从0开始编号，父节点的编号为k，则左子树的编号为2k+1，右子树的编号为2k+2
 * 父节点的编号为（k-1）/2
 */
public class MaxHeap {
    //使用JDK的动态数组（ArrayList）来存储一个最大堆
    List<Integer> data;
    //初始化堆的大小
    public MaxHeap(int size){
        data=new ArrayList<>(size);
    }

    public MaxHeap(int[] arr){
        data=new ArrayList<>(arr.length);
        //1.先将arr的所有元素复制到data数组中
        for (int i:arr) {
            data.add(i);
        }
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }
    public MaxHeap(){
        //构造方法的this调用
        this(10);
    }
    public int peekMax(){
        if (isEmpty()){
            throw new NoSuchElementException("heap is empty!cannot peek");
        }
        return data.get(0);
    }
    public boolean isEmpty(){
        return data.size()==0;
    }

    //根据索引求得父节点的索引
    private int parent(int k){
        return (k-1)>>1;
    }

    //根据索引的到左子树的索引
    private int leftChild(int k){
        return k<<2+1;
    }

    //根据索引的到右子树的索引
    private int rightChild(int k){
        return k<<2+2;
    }

    /**
     * 添加元素
     * @param val
     */
    public void add(int val){
        //1.直接添加元素
        data.add(val);
        //进行元素的上浮操作
        siftUp(data.size()-1);
    }

    /**
     * siftUp(int k):向上调整索引为k的节点，使其满足最大堆的性质
     * 终止条件：当前节点值<=父节点值 ||已经走到根节点值
     * @param k
     */
    private void siftUp(int k) {
        //上浮操作的终止条件
        //循环的迭代条件
        while (k>0 && data.get(k)>data.get(parent(k))){
            //还存在父节点，当前节点的值大于父节点的值
            swap(k,parent(k));
            k=parent(k);
        }
    }

    private void swap(int i, int j) {
        int temp=data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }

    public int extractMax(){
        if (isEmpty()){
            throw new NoSuchElementException("heap is empty! cannot  extract");
        }
        int max=data.get(0);
        //1.将数组末尾的元素顶到堆顶
        data.set(0,data.get(data.size()-1));
        //2，将数组末尾的元素删除
        data.remove(data.size()-1);
        //3.进行元素的下沉操作
        siftDown(0);
        return max;
    }

    private void siftDown(int k) {
        //还存左子树
        while(leftChild(k)<data.size()){
            //左子树的索引
            int j=leftChild(k);
            if(j+1<data.size()&&data.get(j+1)>data.get(j)){
                //此时右树存在且大于左树的值  j对应右子树的索引
                j=j+1;
            }
            //j对应左右子树中较大值的索引
            if(data.get(k)>=data.get(j)){
                //下沉结束
                break;
            }else {
                swap(j,k);
                k=j;
            }
        }
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

